
#include"TreeNode.h"

class Tree
{
	public:
		TreeNode *root;
		int flagX;
		int flagY;
		char c1[20];
		char c2[20];
		char cX;
		char cY;
		Tree();
		bool isEmpty();
		TreeNode* insertChild(TreeNode *p,char value);

			
		void search(TreeNode *p,TreeNode *q);
		
		void outPutTree(TreeNode *p,int i);
	
    private:
		void preOrder(TreeNode *p,int i);
		
};

Tree::Tree()
{
	root=NULL;
}
bool Tree::isEmpty()
{
	return root==NULL;
}


TreeNode*Tree::insertChild(TreeNode *p,char value)
{
	TreeNode *q=NULL;
	if(p!=NULL)
	{
		q=new TreeNode(value);
		if(p->child==NULL)
			p->child=q;
		else
		{
			p=p->child;
			while(p->sibling!=NULL)
				p=p->sibling;
			p->sibling=q;
		}
	}
	return q;
}

void Tree::outPutTree(TreeNode *p,int i)
{
	if(p!=NULL)
	{
		for(int j=0;j<i;j++)
			cout<<"\t";
		cout<<p->data<<endl;
		preOrder(p->child,i+1);
		preOrder(p->sibling,i);
	}
}

void Tree::preOrder(TreeNode *p,int i)
{
	if(p!=NULL)
	{
		if(flagX==0)
		{
			c1[i]=p->data;
		}
		if(flagY==0)
		{
			c2[i]=p->data;
		}
		if(c1[i] == cX)
		{
			flagX=1;
		}
		if(c2[i] == cY)
		{
			flagY=1;
		}
		preOrder(p->child,i+1);
		preOrder(p->sibling,i);
	}
}

char Tree::search(TreeNode *p,TreeNode *q)
{
	flagX=0;
	flagY=0;
	cX=p->data;
	cY=q->data;
	preOrder(root,0);
	int i = 0;
	for(;i < 20;i++)
	{
		if(c1[i]!=c2[i])
		{
			i--;			
		}
	}
return c1[i];
 
}
